﻿// Cheapest Palindrome POJ - 3280.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;
//https://vjudge.csgrandeur.cn/problem/POJ-3280


/*
跟踪所有奶牛是一项棘手的任务，因此农场主约翰安装了一套自动化系统。
他在每头牛身上都安装了一个电子 ID 标签，当奶牛经过扫描仪时，系统就会读取标签内容。
目前，每个 ID 标签的内容都是一个字符串，长度为 M（1 ≤ M ≤ 2,000）个字符，
这些字符来自由 N（1 ≤ N ≤ 26）个不同符号组成的字母表（即小写罗马字母）。

奶牛是调皮的动物，有时会试图通过倒着走来欺骗系统。
ID 为 "abcba "的奶牛无论朝哪个方向走，读数都是一样的，
而 ID 为 "abcb "的奶牛却有可能注册成两个不同的 ID（"abcb "和 "bcba"）。

FJ 希望更改奶牛的 ID 标签，这样无论奶牛从哪个方向走过，它们的读取都是一样的。
例如，"abcb "可以在末尾加上 "a"，形成 "abcba"，这样 ID 就成了双向码（正反读法相同）。
其他一些改变 ID 的方法包括在开头添加三个字母 "bcb"，使 ID 变成 "bcbabcb"，或者去掉字母 "a"，使 ID 变成 "bcb"。
我们可以在字符串的任意位置添加或删除字符，从而得到比原始字符串更长或更短的字符串。

遗憾的是，由于 ID 标签是电子的，每个字符的插入或删除都会产生成本（0 ≤ 成本 ≤ 10,000），
而成本的高低取决于要添加或删除的字符值。
给定奶牛 ID 标签的内容以及插入或删除字母表中每个字符的成本，求改变 ID 标签使其满足 FJ 要求的最小成本。
空 ID 标签被认为满足了正向和反向读取相同的要求。只有有相关代价的字母才能添加到字符串中。

输入
第 1 行 两个空格分隔的整数： N 和 M
第 2 行 这一行包含构成初始 ID 字符串的 M 个字符
第 3...N+2 行：每行包含三个空格分隔的实体：输入字母表中的一个字符和两个整数，这两个整数分别是添加和删除该字符的代价。
输出
第 1 行： 单行，包含一个整数，即更改给定名称标签的最小成本。

3 4
abcb
a 1000 1100
b 350 700
c 200 800

900

提示
如果我们在末尾插入一个 "a"，得到 "abcba"，费用就是 1000。
如果删除开头的 "a"，得到 "bcb"，费用为 1100。
如果我们在字符串的开头插入 "bcb"，费用将是 350 + 200 + 350 = 900，这是最低费用。
*/

int cost[26];
const int N = 2010;
int dp[N][N];
int n, m;
string str;

void solve() {
	memset(dp, 0x3f, sizeof dp);

	for (int i = 0; i < m-1; i++) {
		if (str[i] != str[i + 1]) {
			dp[i][i + 1] = min(cost[str[i]-'a'], cost[str[i + 1]-'a']);
		}
		else {
			dp[i][i + 1] = 0;
		}
		dp[i][i] = 0; dp[i + 1][i + 1] = 0;
	}

	for (int k = 2; k < m; k++) {
		for (int i = 0; i < m-k; i++) {
			int j = i + k;
			if (str[i] == str[j]) {
				dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
			}
			dp[i][j] = min(dp[i][j - 1] + cost[str[j] - 'a'], dp[i][j]);
			dp[i][j] = min(dp[i][j], dp[i + 1][j] + cost[str[i] - 'a']);
		}
	}

	cout << dp[0][m - 1] << endl;
}

int dpfunc(int l, int r) {
	int& ret = dp[l][r];
	if (ret != 0x3f3f3f3f) return ret;
	if (l >= r) { ret = 0; return ret; }
	if(str[l] ==str[r])
		ret = min(ret, dpfunc(l + 1, r - 1));
	ret = min(ret, dpfunc(l, r - 1) + cost[str[r] - 'a']);
	ret = min(ret, dpfunc(l + 1, r) + cost[str[l] - 'a']);

	return ret;
}

void solve1() {
	//记忆化搜索
	memset(dp, 0x3f, sizeof dp);
	cout << dpfunc(0, m - 1) << endl;

}


int main()
{
	cin >> n >> m;
	cin >> str;
	for (int i = 0; i < n; i++) {
		char c; int a, b;
		cin >> c >> a >> b;
		cost[c - 'a'] = min(a, b);
	}

	solve1();

	return 0;
}

 